package 二叉树;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class No230二叉搜索树中第K小的元素 {

    /**
     * 给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
     *
     * 说明：
     * 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
     *
     * 示例 1:
     *
     * 输入: root = [3,1,4,null,2], k = 1
     *    3
     *   / \
     *  1   4
     *   \
     *    2
     * 输出: 1
     * 示例 2:
     *
     * 输入: root = [5,3,6,2,4,null,null,1], k = 3
     *        5
     *       / \
     *      3   6
     *     / \
     *    2   4
     *   /
     *  1
     * 输出: 3
     */

    /**
     * 三种解法:
     * 1.搜索当前节点的左右子树个数定位 (还行,感觉是O(logN)级别的)
     * 2.中序遍历 (比较容易想到 O(n))
     * 3.一直遍历左节点,左节点没了后再遍历右节点 (很好的方法)
     */
    //方法一
    public int kthSmallest(TreeNode root, int k) {
        //怎么做?
        //就一直比较节点个数?一直往左比,直到当前节点的孩子节点数等于k
        //情况:大于k和小于k
        //error这个count不可以一直用,因为这个count包括下一节点的左右子树节点
        int leftCount=countNodesBad(root.left);//获取左子树节点个数
        if(leftCount+1==k)
            return root.val;
        if(leftCount>=k){
            //当前排序太大了,继续往左深入
            return kthSmallest(root.left,k);
        }else{
            //当前排序太小了,得往右深入 (以为这里还可以先左,再往右深入?其实不用因为左孩子的右节点也都是小的)
            return kthSmallest(root.right,k-leftCount-1);//去掉左节点个数和当前节点
        }
    }

    public int countNodesBad(TreeNode root) {
        if(root==null)
            return 0;
        int left=countNodesBad(root.left);
        int right=countNodesBad(root.right);
        return left+right+1;
    }

    //方法二
    public int kthSmallest2(TreeNode root, int k){
        dg(root);
        return list.get(k-1).val;
    }

    List<TreeNode> list=new ArrayList<>();

    private void dg(TreeNode node){
        //中序遍历
        if(node==null)
            return;
        dg(node.left);
        list.add(node);
        dg(node.right);
    }

    //方法三
    public int kthSmallest3(TreeNode root, int k){

        Stack<TreeNode> stack=new Stack<>();
        TreeNode node=root;
        int count=0;

        //一直加到最左边,然后再慢慢吐出进行统计

        while (true){
            while (node!=null){
                stack.add(node);
                node=node.left;
            }
            //加到了最左边,开始慢慢吐
            TreeNode pop = stack.pop();
            count++;
            if(k==count)
                return pop.val;
//            node=pop.right;
            if(pop.right!=null) {
                node=pop.right;
                //stack.add(pop.right);//那当前右子树的孩子节点呢?所以不能单独加
            }
        }
    }

    public static void main(String[] args) {
        No230二叉搜索树中第K小的元素 n=new No230二叉搜索树中第K小的元素();
        TreeNode nodeByArr = TreeNode.getNodeByArr(new Integer[]{3,1,4,null,2});
        int i = n.kthSmallest3(nodeByArr, 3);
        System.out.println(i);
    }

}